/*
LICENCIA
========
Copyright (C) 2009

Autores:

Carlos Alberto Martínez Gadea   <camg6@alu.ua.es>
Manel Simon Martínez            <msm85@alu.ua.es>

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#include "TLista.h"
#include "util.h"

using namespace std;

/*************************************************
				CLASE TLista
*************************************************/

/* Constructor por defecto de TLista
    - Crea la partición para el SO
    - Crea un hueco de 640
    - Asigna el algoritmo "primer_hueco"
*/
TLista::TLista() : alg_vigente(kALG_PR), hueco_total(640)
{
    cabeza = cola = NULL;

    TListaNodo so(contador++, 384,640), hueco(contador++, 640,0);

    so.SetProg("SO");
    so.SetSO();
    so.SetAsign(true);

    InsCabeza(so);
    InsCabeza(hueco);
    ultimo_insertado = cabeza;
}

TLista::TLista(const TLista& l) : alg_vigente(l.GetAlgoritmo())
{
    cabeza = cola = NULL;

    if( !l.EsVacia() )
    {
        TListaNodo *n = l.cabeza;

        while(n != NULL)
        {
            TListaNodo nuevo(n->id,n->reg_limite,n->reg_base);
            if(cabeza == NULL)
            {
                    InsCabeza(nuevo);
            }
            else
            {
                    InsertarD(nuevo,cola);
            }
            n = n -> sig;
        }

        ultimo_insertado = cabeza;
    }
}

TLista::~TLista()
{
    TListaNodo* nodo = cabeza, *aux;

    while(nodo != NULL)
    {
        aux = nodo;
        nodo = nodo -> sig;
        delete aux;
        aux = NULL;
    }

    cabeza = cola = ultimo_insertado = NULL;
}

TLista& TLista::operator=(const TLista &l)
{
    if( this != &l )
    {
        (*this).~TLista();

        alg_vigente = l.GetAlgoritmo();
        cabeza = cola = NULL;

        if( !l.EsVacia() )
        {
            TListaNodo *n = l.cabeza;

            while(n != NULL)
            {
                TListaNodo nuevo(n->id,n->reg_limite,n->reg_base);
                if(cabeza == NULL)
                {
                    InsCabeza(nuevo);
                }
                else
                {
                    InsertarD(nuevo,cola);
                }
                n = n -> sig;
            }

            ultimo_insertado = cabeza;
        }
    }
    return *this;
}

/* Asignación del algoritmo */
void TLista::SetAlgoritmo(string algoritmo, ofstream& salida)
{
    if( algoritmo == "primer_hueco" )
    {
         alg_vigente = kALG_PH;
    }
    else if( algoritmo == "mejor_hueco" )
    {
        alg_vigente = kALG_MH;
    }
    else if( algoritmo == "peor_hueco" )
    {
        alg_vigente = kALG_PH;
    }
    else
    {
        alg_vigente = kALG_SH;
    }

    salida << kACTIVA << algoritmo << endl;
}

/* Devuelve el hueco acorde al algoritmo "peor_hueco" (hueco más grande) */
TListaNodo* TLista::PeorHueco()
{
    TListaNodo* hueco = GetCabeza();
    TListaNodo* max = NULL;

    while(hueco != NULL)
    {
        if(!hueco -> Asignado() && max == NULL)                                         /* Asigna a max el primer hueco */
            max = hueco;
        else if(!hueco -> Asignado() && hueco -> GetRegLim() > max -> GetRegLim())      /* Asigna el maximo hueco */
            max = hueco;

        hueco = hueco -> GetSig();
    }

    return max;
}

/* Devuelve el hueco acorde al algoritmo "mejor_hueco" (que menos espacio deja) */
TListaNodo* TLista::MejorHueco(int tam_prog)
{
    TListaNodo* hueco = GetCabeza();
    TListaNodo* mejor = NULL;

    while(hueco != NULL)
    {
        if(!hueco -> Asignado() && mejor == NULL && tam_prog <= hueco -> GetRegLim())                                       /* Asigna a 'mejor' el primer hueco */
            mejor = hueco;
        else if(!hueco -> Asignado()                                /* Si el nodo es un hueco (no asignado),    */
                && tam_prog <= hueco -> GetRegLim()                 /* el programa cabe en el hueco y           */
                && mejor -> GetRegLim() > hueco -> GetRegLim())     /* el hueco es más pequeño que 'mejor',     */
            mejor = hueco;                                          /* se asigna a 'mejor' dicho nodo           */

        hueco = hueco -> GetSig();
    }

    return mejor;
}

/* Esta func. devolverá el TListaNodo*(que sea hueco) siguiente al TListaNodo* que
 * esté en la lista indicando la referencia al último insertado */
TListaNodo* TLista::SiguienteHueco(int tam_prog)
{
    TListaNodo *sig_hueco = NULL, *n = ultimo_insertado;

    /* Recorre la lista a partir del último nodo insertado
       hasta encontrar un hueco donde quepa */
    do {

        if( !n -> Asignado() && tam_prog <= n -> GetRegLim() )  /* Si n es un hueco y el programa cabe en él */
            sig_hueco = n;                                      /* guardamos en 'sig_hueco'                 */

        n = n -> sig;

        if( n -> IsSO() )
            n = cabeza;

    } while(n != ultimo_insertado && sig_hueco == NULL);

    return sig_hueco;
}

/* Este algoritmo devolverá el primer hueco libre en la lista de particiones */
TListaNodo* TLista::PrimerHueco(int tam_prog)
{
    bool encontrado = false;

    TListaNodo* hueco = GetCabeza();
    TListaNodo* aux = NULL;

    /* Recorre la list hasta encontrar el primer hueco */
    while(hueco != NULL && !encontrado)
    {
        if(!hueco -> Asignado() && tam_prog <= hueco -> GetRegLim())    /* Si cabe el programa en el hueco */
        {
            aux = hueco;
            encontrado = true;
        }
        else
            hueco = hueco -> GetSig();
    }

    return aux;
}

/* Carga el proceso contenido en 'n' en el nodo 'hueco' */
bool TLista::CargarProceso(TListaNodo* hueco, const TListaNodo& n)
{
    bool cargado = false, encontrado = false;

    TListaNodo* nodo = new TListaNodo(n);
    TListaNodo* ant = NULL;
    TListaNodo* aux = GetCabeza();

    while(aux != NULL && !encontrado)                                           /* Busca el nodo anterior a 'hueco' */
    {
        ant = aux;
        if(aux -> GetSig() != hueco)
            aux = aux -> GetSig();
        else
            encontrado = true;
    }

    if(hueco != NULL && hueco -> GetRegLim() == nodo -> GetRegLim())            /* Si el hueco es del mismo tamaño que el programa */
    {
        hueco -> SetAsign(true);
        hueco -> SetProg(nodo -> GetProg());

        cargado = true;
    }
    else if(hueco != NULL && nodo -> GetRegLim() < hueco -> GetRegLim())        /* Si el hueco es más grande que el programa */
    {
        if(hueco -> GetRegBase() == 0)                                          /* Si el hueco empieza en la dirección física 0 */
            cabeza = nodo;
        else
            ant -> SetSig(nodo);

        nodo    -> SetRegBase(hueco -> GetRegBase());                           /* Actualizamos el reg. base al comienzo del hueco */
        hueco   -> SetRegBase(hueco -> GetRegBase() + nodo -> GetRegLim());     /* Actualizamos el reg. base del hueco (sumamos el reg. lim del p) */
        hueco   -> SetRegLim(hueco -> GetRegLim() - nodo -> GetRegLim());
        nodo    -> SetSig(hueco);
        nodo    -> SetAsign(true);

        cargado = true;
    }

    /* Si el nodo se carga, se actualiza la referencia al último insertado
       y el hueco total disponible */
    if(cargado)
    {
        hueco_total -= nodo -> GetRegLim();
        ultimo_insertado = nodo;
    }

    return cargado;
}

/* En esta func. siempre que sea posible, creará una partición con los datos
 * de entrada y según el algoritmo vigente*/
void TLista::ReservarEspacio(string entrada, ofstream &salida)
{
    string programa;
    int tam_prog;
    TListaNodo* hueco = NULL;

    programa = ParseaNomProg(entrada);  /* Guarda el nombre del programa    */
    tam_prog = ParseaTamProg(entrada);  /* Guarda el tamaño del programa    */

    TListaNodo n(programa, tam_prog);   /* Crea el nodo con el nombre y el tamaño del programa */

    /* Guarda el hueco en función del algoritmo vigente */
    switch(alg_vigente)
    {
        case kALG_PR:
            hueco = PrimerHueco(tam_prog);
            break;

        case kALG_MH:
            hueco = MejorHueco(tam_prog);
            break;

        case kALG_PH:
            hueco = PeorHueco();
            break;

        case kALG_SH:
            hueco = SiguienteHueco(tam_prog);
            break;
    }

    /* Se escribe en el fichero de salida tanto si se ha cargado como si no */
    if(hueco != NULL && CargarProceso(hueco, n))
        salida << kRES << tam_prog << kPARA << programa << kPUNTO << endl;
    else
        salida << kNO_HUECO << tam_prog << kPARA << programa << kPUNTO << endl;

}

/* Evalúa si no existe ningun hueco donde quepa una partición de tamaño 'tam_prog' */
bool TLista::NecesarioCompactar(int tam_prog)
{
    bool compactar = true;
    TListaNodo* n = cabeza;

    while( compactar && !n -> IsSO() )
    {
        /* Si existe un hueco de tamaño mayor o igual al requerido, no se compacta */
        if( !n -> Asignado() && n -> reg_limite >= tam_prog )
        {
            compactar = false;
        }
        n = n -> GetSig();
    }

    return compactar;
}

/* Aquí se intenta crear una partición en un hueco y en caso de no existir ningún
 * hueco para ella, compactaremos la lista de particiones y volveremos a intentar,
 * siendo posible que no exista tamaño suficiente */
void TLista::ReservaYCompacta(string entrada, ofstream &salida)
{
    int tam_prog = ParseaTamProg(entrada);
    string programa = ParseaNomProg(entrada);

    if( hueco_total >= tam_prog )
    {
        if( NecesarioCompactar(tam_prog) )
        {
            Compacta();
            salida << kCOMPACT << programa << kPUNTO << endl;
        }
        ReservarEspacio(entrada,salida);
    }
    else
    {
        salida << kNO_EX << tam_prog << kMEM << programa << kPUNTO << endl;
    }
}

/* Introducimos TListaNodo(n) en la cabeza de la lista */
bool TLista::InsCabeza(const TListaNodo& n)
{
    bool insertado=false;
    TListaNodo* nodo = new TListaNodo(n);
    TListaNodo* aux;

    if(nodo)
    {
        insertado = true;
        if(EsVacia())
        {
            cabeza = cola = nodo;
        }
        else
        {
            aux = cabeza;
            nodo -> sig = cabeza;
            cabeza = nodo;
        }
    }

    return insertado;
}

/* Se insertará TListaNodo(n) a la derecha del nodo al que apunte TListaNodo*(ref) */
bool TLista::InsertarD(const TListaNodo& n,TListaNodo* ref)
{
    bool insertado=false;
    TListaNodo* aux = cabeza;

    while(aux != NULL && !insertado)
    {
        if(aux == ref)
        {
            TListaNodo* nodo = new TListaNodo(n);
            if( ref -> sig == NULL )
            {
                ref -> sig = nodo;
                cola = nodo;
            }
            else
            {
                aux = ref -> sig;
                ref -> sig = nodo;
                nodo -> sig = aux;
            }
            insertado = true;
        }
        aux = aux -> sig;
    }

    return insertado;
}

/* Liberamos la partición donde esté el programa 'p' convirtiéndola de nuevo en
 * hueco y fusionando con los de su alrededor si fueran huecos */
bool TLista::LiberarParticion(string p)
{
    TListaNodo  *n = cabeza, *ant = NULL;
    bool liberado = false;

    while( n != NULL && !liberado )
    {
        if( n -> GetProg() == p )
        {
            n -> SetProg("\0");                 /* Borramos el nombre del programa                      */
            n -> SetAsign(false);               /* Actualizamos el booleano de asignación               */
            hueco_total += n -> GetRegLim();    /* Aumenta la variable 'hueco_total'                    */
            JuntarHuecos(n, ant);               /* Se juntan los huecos contiguos si fuera necesario    */
            liberado = true;
        }
        ant = n;
        n = n -> GetSig();
    }

    return liberado;
}

/* Esta func. unirá los nodos a los que apunten TListaNodo*(hueco), TListaNodo* (sig)
 * y TListaNodo*(ant) si es necesario */
bool TLista::JuntarHuecos(TListaNodo* hueco , TListaNodo* ant)
{
    bool unidos = false;
    TListaNodo *sig = hueco -> GetSig();

    if( ant == NULL )
    {
        /* Caso en que no existe "ant" y "sig" es hueco */
        if( !sig -> IsSO() && !sig -> Asignado() )
        {
            hueco -> SetRegLim(hueco -> GetRegLim() + sig -> GetRegLim());
            hueco -> SetSig(sig -> GetSig());
            delete sig;
            sig = NULL;
            unidos = true;
        }
        /* Caso en que no existe "ant" y "sig" no es hueco */
        else
        {
            unidos = true;
        }
    }
    else
    {
        /* Caso en que existe "ant" y es hueco pero "sig" no es hueco */
        if( !ant -> Asignado() && ( sig -> Asignado() || sig -> IsSO() ) )
        {
            ant -> SetRegLim(ant -> GetRegLim() + hueco -> GetRegLim());
            ant -> SetSig(sig);
            delete hueco;
            hueco = NULL;
            unidos = true;
        }
        /* Caso en que existe "ant" y es hueco y "sig" tambien */
        else if( !ant -> Asignado() && !sig -> Asignado() && !sig -> IsSO() )
        {
            ant -> SetRegLim(ant -> GetRegLim() + hueco -> GetRegLim() + sig -> GetRegLim());
            ant -> SetSig(sig -> GetSig());
            delete hueco;
            hueco = NULL;
            delete sig;
            sig = NULL;
            unidos = true;
        }
        /* Caso en que existe "ant" y no es hueco pero "sig" es hueco */
        else if( ant -> Asignado() && !sig -> Asignado() && !sig -> IsSO() )
        {
            hueco -> SetRegLim(hueco -> GetRegLim() + sig -> GetRegLim());
            hueco -> SetSig(sig -> GetSig());
            delete sig;
            sig = NULL;
            unidos = true;
        }
    }

    /* Actualizamos el ultimo_insertado, necesario para el algoritmo "siguiente_hueco" */
    if( ultimo_insertado == NULL )
        ultimo_insertado = hueco;

    return unidos;
}

/* Func. encargada de gestionar el comando M donde se nos solicitará la ampliación de una partición */
void TLista::AmpliarParticion(string entrada, ofstream& salida)
{
    string programa;
    int incremento, tam_actual = 0;
    bool ampliado = false;
    TListaNodo *n = cabeza, *sig = cabeza -> sig, *ant = NULL;

    programa = ParseaNomProg(entrada);
    incremento = ParseaTamProg(entrada);

    //En caso de existir tamaño para el incremento se realizará, si no mostraremos que no ha sido posible
    if( hueco_total >= incremento )
    {
        //Llegamos al nodo donde esta el programa
        while( n -> prog != programa )
        {
            if( n -> prog == programa )
                tam_actual = n -> reg_limite;
            ant = n;
            n = n -> sig;
            sig = n -> sig;
        }

        // Controla el tamaño de los huecos contiguos
        int tam_huecos = sig -> reg_limite;
        if( ant != NULL )
            tam_huecos += ant -> reg_limite;

        //Caso en que la ampliación ocupa total o parcialmente el hueco posterior a "n"
        if( n -> prog == programa && sig != NULL && !sig -> asignado && sig -> reg_limite >= incremento )
        {
            sig -> reg_base += incremento;
            sig -> reg_limite -= incremento;
            n -> reg_limite += incremento;
            if( sig -> reg_limite == 0 )
            {
                n -> sig = sig -> sig;
                delete sig;
                sig = NULL;
            }
            hueco_total -= incremento;
            ampliado = true;
            salida << kAMP << programa << kCON << incremento << kPUNTO << endl;
        }

        //Caso en que la ampliación ocupa total o parcialmente los huecos anterior y posterior a "n"
        if( n -> prog == programa && sig != NULL && !sig -> asignado && ant != NULL && !ant -> asignado && !ampliado && tam_huecos >= incremento )
        {
            TListaNodo nuevo(programa,n->reg_limite + incremento);
            LiberarParticion(programa);
            CargarProceso(ant,nuevo);
            ampliado = true;
            salida << kAMP << programa << kCON << incremento << kPUNTO << endl;
        }

        //Caso en que la ampliación ocupa total o parcialmente el hueco anterior a "n"
        if( n -> prog == programa && ant != NULL && !ant -> asignado && ant -> reg_limite >= incremento && !ampliado)
        {
            n -> reg_base -= incremento;
            ant -> reg_limite -= incremento;
            n -> reg_limite += incremento;
            if( ant -> reg_limite == 0 )
            {
                TListaNodo nuevo(programa,n->reg_limite);
                LiberarParticion(programa);
                CargarProceso(ant,nuevo);
            }
            hueco_total -= incremento;
            ampliado = true;
            salida << kAMP << programa << kCON << incremento << kPUNTO << endl;
        }

        //Caso en que la ampliación requiere de compactación para poder llevarse a cabo
        if( n -> prog == programa && !ampliado )
        {
            salida << kNO_HUECO << incremento << kPARA << programa << kPUNTO << endl;
            salida << kCOMYAMP << programa  << kPUNTO << endl;
            tam_actual = n -> reg_limite;
            LiberarParticion(programa);

            string aux = "  " + programa + " ";
            stringstream flujo;
            flujo << (tam_actual + incremento);
            string mystr=flujo.str();
            aux += mystr;

            ReservaYCompacta(aux,salida);
        }
    }
    else
    {
        salida << kNOAMPLI << incremento << kPARA << programa << endl;
    }
}

//Func. que devolverá el nº de particiones que se dispone en la lista de particiones
int TLista::Long() const
{
    int longitud = 0;
    TListaNodo *aux = cabeza;

    while( aux != NULL )
    {
        longitud++;
        aux = aux -> sig;
    }

    return longitud;
}

/* Función gestora del comando D */
void TLista::AccederDireccion(string p, int dir, ofstream& file)
{
    TListaNodo* n = GetCabeza();
    bool encontrado = false;

    /* Bucle que busca el nodo que posee el programa 'p' */
    while(n != NULL && !encontrado)
    {
        if(n -> GetProg() == p)
        {
            encontrado = true;
            /* Si la dirección 'dir' no sobrepasa el registro límite, se permite el acceso.
               En caso contrario, se da un mensaje de error */
            if(dir < n -> GetRegLim())
                file << p << kACCEDE << dir << kOK;
            else
                file << p << kACCEDE << dir << kERROR;
        }

        n = n -> GetSig();

    }

}

/* Func. encargada de realizar la compactación de particiones, es decir, se unirán
 * TODOS los huecos disponibles en uno sólo */
void TLista::Compacta()
{
    TListaNodo* hueco = GetCabeza();
    TListaNodo* ant = NULL;
    TListaNodo* aux = NULL;

    /* Borra todos los huecos almacenando su tamaño */
    while(hueco != NULL)
    {
        if(!hueco -> Asignado() && ant == NULL)     /* Hay un hueco en la cabeza */
        {
            cabeza = hueco -> GetSig();
            aux = hueco -> GetSig();

            delete hueco;
            hueco = aux;
        }
        else if(!hueco -> Asignado())               /* Existe nodo anterior */
        {
            ant -> SetSig(hueco -> GetSig());
            aux = hueco -> GetSig();

            delete hueco;
            hueco = aux;
        }
        ant = hueco;
        hueco = hueco -> GetSig();
    }

    /* Crea un nuevo nodo al comienzo de la lista */
    TListaNodo* nodo = new TListaNodo();
    nodo -> SetRegLim(hueco_total);             /* Se le asigna el tamaño total de los huecos borrados */
    nodo -> SetId(++contador);

    aux = cabeza;
    cabeza = nodo;
    nodo -> SetSig(aux);

    AjustaReg();                                /* Ajusta los registros de toda la lista */
}

/* Función auxiliar que recalcula todos los registros base */
void TLista::AjustaReg()
{
    TListaNodo* it = GetCabeza() -> GetSig(); // Empezamos en el segundo nodo
    TListaNodo* ant = GetCabeza();

    while(it != NULL && !it -> IsSO())
    {
        it -> SetRegBase(ant -> GetRegBase() + ant -> GetRegLim());
        ant = it;
        it = it -> GetSig();
    }
}

/*************************************************
				CLASE TListaNodo
*************************************************/

/* Crea un nodo por defecto (vacío) */
TListaNodo::TListaNodo() : reg_base(0), reg_limite(0), id(-1), asignado(false), so(false)
{
    sig = NULL;
}

/* Crea un nodo con el id 'n' y los registros facilitados */
TListaNodo::TListaNodo(int n, int limite, int base) : reg_base(base), reg_limite(limite), id(n), so(false), asignado(false)
{
    sig = NULL;
}

/* Crea un nodo y le asigna el programa 'p' (Constructor más utilizado) */
TListaNodo::TListaNodo(string p, int lim) : reg_base(0), reg_limite(lim), prog(p), so(false), asignado(true), id(++contador)
{ }

TListaNodo::TListaNodo(const TListaNodo& n)
{
    reg_base = n.GetRegBase();
    reg_limite = n.GetRegLim();
    id = n.GetId();
    asignado = n.Asignado();
    sig = n.sig;
    so = n.so;
    prog = n.prog;
}

TListaNodo::~TListaNodo()
{
    sig = NULL;
}

TListaNodo& TListaNodo::operator=(const TListaNodo& n)
{
    if(this != &n)
    {
        reg_base = n.GetRegBase();
        reg_limite = n.GetRegLim();
        id = n.GetId();
        asignado = n.Asignado();
        prog = n.prog;
        sig = n.GetSig();
    }

    return *this;
}
